package middle;

import sword.offer.common.Node;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点
 *
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ConvertBinarySearchTreeToSortedDoublyLinkedList {
    class Solution {
        private Node head;
        private Node pre;
        public Node treeToDoublyList(Node root) {
            if(root == null){
                return null;
            }
            recur(root);
            head.left = pre;
            pre.right = head;
            return head;
        }

        private void recur(Node root){
            if(root == null){
                return ;
            }
            recur(root.left);
            if(head == null){
                head = root;
            }
            if(pre != null){
                pre.right = root;
                root.left = pre;
            }
            pre = root;
            recur(root.right);
        }
    }
}
